//单链表基本运算算法
#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef struct LNode  
{
	ElemType data;
	struct LNode *next;		//指向后继结点
} LinkNode;					//声明单链表结点类型


void CreateListR(LinkNode *&L,ElemType a[],int n)
//尾插法建立单链表
{
	LinkNode *s,*r;
	L=(LinkNode *)malloc(sizeof(LinkNode));  	//创建头结点
	L->next=NULL;
	r=L;					//r始终指向终端结点,开始时指向头结点
	for (int i=0;i<n;i++)
	{	
		s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点s
		s->data=a[i];
		r->next=s;			//将结点s插入结点r之后
		r=s;
	}
	r->next=NULL;			//终端结点next域置为NULL
}

void InitList(LinkNode *&L)
{
	L=(LinkNode *)malloc(sizeof(LinkNode));  	//创建头结点
	L->next=NULL;
}

void DestroyList(LinkNode *&L)
{
	LinkNode *pre=L,*p=pre->next;
	while (p!=NULL)
	{	free(pre);
		pre=p;
		p=pre->next;
	}
	free(pre);	//此时p为NULL,pre指向尾结点,释放它
}

int ListLength(LinkNode *L)
{
	LinkNode *p=L;int i=0;
	while (p->next!=NULL)
	{	i++;
		p=p->next;
	}
	return(i);
}
void DispList(LinkNode *L)
{
	LinkNode *p=L->next;
	while (p!=NULL)
	{	printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
}

void BubbleSort(LinkNode *&L,int n)
{
	LinkNode*pre = L;
	LinkNode*p = pre->next;
	LinkNode*nex = p->next;
	int flag = 1;
	for(int i = 0;i<n;i++)
	{
		flag = 1;
		pre = L;
		p = pre->next;
		nex = p->next;		
		for(int k = 9-i;k>0;k--)//while(p->next)
		{
			if(p->data>nex->data)
			{
				p->next = nex->next;
				nex->next = p;
				pre->next = nex;
				flag = 0;
			}
			pre = pre->next;
			p = pre->next;
			nex = p->next;
		}
		if(flag==1)
		{
			break;
		}
	}
	
}


int main()
{
	int a[10] = {9,5,8,6,4,7,0,1,3,2};
	LinkNode*L = NULL;
	CreateListR(L,a,10);
	printf("(1)设计算法实现对单链表进行简单排序。注意应通过修改指针来实现，而不是交换数据元素，以发挥链表的操作优势。\n");
	
	
	printf("初始化之后单链表为：");
	DispList(L);
	//冒泡排序
	
	BubbleSort(L,10);
	
	printf("排序之后单链表为：");
	DispList(L);
	
	
	//销毁单链表
	DestroyList(L);
	return 0;
}
